import List

-- ejercicio 2

subconjuntos :: [a] -> [[a]]
subconjuntos []     = [[]]
subconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub
    where sub = subconjuntos xs

f :: (Eq a) => [a] -> Int -> [[a]]
f alfabeto k = filter (restriccion) xs
		where
			restriccion x = length(x) <= k 
			xs = nub (subconjuntos (mult alfabeto alfabeto k))
			mult xs _ 0 = xs
			mult xs ys (n+1) = mult (xs++ys) ys n  

-- ejercicio 3

catalan :: Int -> Int
catalan 0 = 1
catalan n = catalanRec 1 n 
	where catalanRec k p 
			| k == p = catalan(k-1) * catalan 0
			| otherwise = catalan(k-1) * catalan (p-k) + catalanRec (k+1) p 

-- ejercicio 4

subSec :: Int -> [Int] -> [Int]
subSec x [] = [x]
subSec x (y:ys) 
	| x <= y = x:( subSec y ys)
	| otherwise = subSec x ys

s :: [Int] -> [[Int]] 
s [] = [[]]
s (x:xs) = rs:(s xs)
	where rs = subSec x xs

res :: [Int] -> [Int]
res xs = sol zs
	where 
		  zs = s xs
		  sol [[]] = []
		  sol (x:xs) = masGrande x xs
		  masGrande ls [] = ls
		  masGrande ls (d:ds) 
				| length(ls) < length(d) = masGrande d ds
				| otherwise = masGrande ls ds	

-- ejercicio 5

mergeSort:: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge ys zs 
			   where
					ys = mergeSort (take half xs)
					zs = mergeSort (drop half xs)	
					half = div size 2 
					size = length xs

merge:: (Ord a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x < y = [x] ++ merge xs (y:ys)
					| y < x = [y] ++ merge (x:xs) ys
					| otherwise = [x,y] ++ merge xs ys	

mejorPivote :: (Ord a) => [a] -> a
mejorPivote xs = pivote(op)
	where 
		op = mergeSort xs
		pivote ws 
			| mod (length ws) 2 == 0 = last (mitad ws) -- la secuencia es par
			| otherwise = head (final ws)
		mitad qs = take (div (length qs) 2) qs
		final qs = drop (div (length qs) 2) qs
	  		  
	 
